package com.alg;

import java.util.LinkedList;
import java.util.List;

/**
 * @author: sun.hongliang
 * @create: 2020/02/05 13:02
 */
public class StringTest {
    public static void main(String[] args) {
        System.out.println(Integer.parseInt("02"));
    }

    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;
        char[] chars = s.trim().toCharArray();
        reverse(chars, 0, chars.length - 1);
        reverseSingle(chars);
        return new String(chars);
    }

    private void reverseSingle(char[] chars) {
        int start = 0, end = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                end = i;
            }
            if (end > start) {
                reverse(chars, start, end);
                start = end;
            }
        }
    }

    private void reverse(char[] chars, int start, int end) {
        while (start < end) {
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            start++;
            end--;
        }
    }

    public List<Integer> majorityElement(int[] nums) {
        int x = 0, y = 0, cx = 0, cy = 0;
        for (int num : nums) {
            if (cx == 0) {
                x = num;
                cx = 1;
            } else if (cy == 0) {
                y = num;
                cy = 1;
            } else if (x == num) {
                cx++;
            } else if (y == num) {
                cy++;
            } else {
                cx--;
                cy--;
            }
        }
        cx = 0;
        cy = 0;
        for (int num : nums) {
            if (num == x) {
                cx++;
            } else if (num == y) {
                cy++;
            }
        }
        List<Integer> res = new LinkedList<>();
        if (cx > nums.length / 3) {
            res.add(x);
        }
        if (cy > nums.length / 3) {
            res.add(y);
        }
        return res;
    }

}
